package fun.coding.leetcode;

import java.util.ArrayList;
import java.util.List;

public class SumRootToLeafNumbers {

	public static void main(String[] args) {

	}
	
	/* this is also a good way to solve it.
	    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode root, int prev){
        if(root == null) {
            return 0;
        }

        int sum = root.val + prev * 10;
        if(root.left == null && root.right == null) {
            return sum;
        }

        return dfs(root.left, sum) + dfs(root.right, sum);
    } 
	 */
	
    public int sumNumbers(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        helper(root, res, 0);
        
        int sum = 0;
        for (int i : res) {
        	sum += i;
        }
        
        return sum;
    }
    
    public void helper(TreeNode root, List<Integer> res, int cur) {
    	if (root == null) return;
    	
    	cur = cur * 10 + root.val;
    	
    	// if it is leaf
    	if (root.left == null && root.right == null) {
    		res.add(cur);
    		return;
    	}
    	
    	helper(root.left, res, cur);
    	helper(root.right, res, cur);
    }
}
